package heap;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

/*
 *@description 查找和最小的 K 对数字
 *@author hkfan
 *@version 1.0
 *@create 2025/6/23 16:50
 */
public class LeetCode_373 {

    @Test
    public void test(){
        kSmallestPairs(new int[]{1},new int[]{3,5,6,7,8,100},4);
    }

    class Node{
        int x;
        int y;
        int y_index;

        public Node(int x, int y,int y_index) {
            this.x = x;
            this.y = y;
            this.y_index = y_index;
        }
    }

    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //1. 统计所有的序列,加入堆中
        PriorityQueue<Node> minQueue = new PriorityQueue<>((node1,node2)->{
            return (node1.x+node1.y-node2.x-node2.y);
        });
        for (int i = 0; i < Math.min(k, nums1.length); i++) {
            minQueue.add(new Node(nums1[i],nums2[0],0));
        }
        //2. 输出结果
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            Node node = minQueue.poll();
            list.add(node.x);
            list.add(node.y);
            res.add(list);
            if (node.y_index+1<nums2.length){
                minQueue.add(new Node(node.x,nums2[node.y_index+1], node.y_index+1));
            }
        }
        return res;
    }
}